Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ja, wir wenden uns nunmehr zu der Syntax- und der operationalen Semantik von Therm-

ersetzungssystem. Wenn ich operationale Semantik sage, dann impliziert das schon,

dass ich ein Therm- ersetzungssystem mehr oder weniger als ein Programm ansehe.

Die Syntax wird relativ trivial sein, das wird uns nicht viel Zeit kosten. Also das,

was ein bisschen Anlauf benötigt ist. Ja, im Prinzip das, was wir uns letztes mal informell

klar gemacht haben, so nach dem Motto jeder weiß, was es heißt einen Therm umzuformen,

das können wir seit der achten Klasse, das nun also in formal analysierbare Begriffe zu gießen.

So, wir fangen an mit einem Überblick über Dinge, die man so mit binären Relationen machen kann.

Das werden Sie größtenteils vielleicht kennen, teilweise vielleicht auch nicht.

So eine Relation entspricht dem Pfeil, den wir in der letzten Sitzung schon gesehen haben.

Wir wollen also Therm umformen und das gibt also Anlass zu so einer Rechts-

links-Relation vor der Umformung, nach der Umformung. Und das ist der Grund,

warum wir uns jetzt erst mal ein ganzes Ende mit Relationen abstrakt beschäftigen.

Vieles von dieser Theorie der Thermersetzungssysteme kann man durchziehen,

ohne zu wissen, dass die Dinge, die man da manipuliert, tatsächlich Terme sind.

Man kann das völlig abstrakt lassen, das hat auch einen Namen als Gebiet, das heißt abstract rewriting.

Da sage ich nur, ich nehme irgendwelche Entitäten, in deren Struktur ich gar nicht weiter reingucke

und forme die irgendwie um. Und umformen heißt einfach nur, ich gehe solche Relationen entlang.

Und dann gibt es relativ wenige Sachen, die nachher spezifisch zur Umformung von Termen sind

und es verzweigt auch ein bisschen. Es gibt auch zum Beispiel ein ganzes Gebiet,

was sich mit der Umformung nicht etwa von Termen, sondern von Graphen beschäftigt.

Daher also wie gesagt jetzt ein paar Dinge zu völlig abstrakten Relationen.

Und wie gesagt größtenteils müsste es im Wesentlichen den Charakter einer Erinnerung haben.

Genauer gesagt interessieren wir uns für binäre Relationen und zwar binäre Relationen auf ein und derselben Grundmenge.

So eine binäre Relation ist also einfach eine Teilmenge typischer Buchstabe R oder vielleicht mal S, wenn wir was anderes brauchen oder U.

Das Kreuzprodukt einer Grundmenge X mit sich selbst. So etwas ist also genauer gesagt eine binäre Relation auf X.

Nehmen wir mal ein Beispiel her. Warum sind binäre Relationen solche Teilmengen?

Ich kann zum Beispiel also die kleiner Gleichrelation, das ist ja eine binäre Relation, wenn ich jetzt mal sage,

ich nehme die auf den natürlichen Zahlen, dann ist die kleiner Gleichrelation auf den natürlichen Zahlen also eine Teilmenge von N Kreuz N.

Etwas tautologisch kann ich schreiben, kleiner Gleich ist eben diejenigen Teilmenge von N Kreuz N,

die nun genau gerade diejenigen Paare von Zahlen N, M enthält, sodass N kleiner Gleich M ist.

Dies ist die Stelle, wo ich sage, das ist so ein bisschen tautologisch. Das ist also die Art, wie wir zwischen diesen beiden Schreibweisen konvertieren.

Wir haben also einerseits diese Verwendung der Relationen, die wir typischerweise infix schreiben,

zwischen zwei Elemente, die halt in Relation stehen und dieser Sichtweise auf eine Relation als eine Teilmenge eines Kreuzproduktes.

Der Rest unserer Erinnerung wird also bestehen in erstens Eigenschaften, die so Relationen haben können

und zweitens Konstruktionen, die wir auf Relationen machen können.

Also ich liste jetzt einfach mal ein paar hoffentlich größtenteils bekannte Eigenschaften auf, die so eine Relation haben kann.

Genauer gesagt eben eine Relation auf irgendeiner Grundmenge x. So ein Ding heißt.

Die einfachste Eigenschaft, die man sich vielleicht ausdenken kann, ist die Reflexivität. Das sollten eigentlich alle kennen.

R ist reflexiv, genau dann, wenn für alle Elemente klein x unserer Grundmenge groß x gilt x groß R x.

Nicht nochmal, das hier ist eine Kurzschreibweise dafür, dass das Paar x, x Element von Groß R ist.

Eine weitere Eigenschaft, die eine Relation haben kann, ist die Symmetrie.

Also eine Relation ist symmetrisch, genau dann, wenn für je zwei Elemente x, y dieses Grundbereichs groß x gilt,

wenn x in Relation R zu y steht, dann auch umgekehrt.

Weitere bekannte Eigenschaft ist Transitivität. Also R heißt transitiv, wenn für je drei Elemente x, y, z des Grundbereichs groß x gilt,

wenn die so eine Kette bilden, also x in Relation Groß R zu y steht und y außerdem in Relation Groß R zu z steht, dann steht x in Relation Groß R zu z.

So, dann kommt einer, den kennen Sie vielleicht noch nicht.

Groß R heißt eine Präordnung, wenn R reflexiv und transitiv ist.

So, einmal um das Publikum zu wecken, warum heißt das eine Präordnung, was würde ich von einer tatsächlichen Ordnung zusätzlich verlangen?